#include "udt_interface.h"
#include <stdlib.h>
#include <memory.h>
#include <math.h>
#include <stdio.h>
#include <assert.h>

UDTIntervalSet gIntSet;

void udt_DataLinkSet_to_IntervalSet(UDTDataLinkSet *pLink, UDTIntervalSet *pIntSet, int attribute)
{
	int i;
    pIntSet->interval_count = pLink->linkCount;
    pIntSet->label_count = pLink->labelCount;
    for (i = 0; i < pLink->linkCount; ++i) {
        pIntSet->intervals[i].low = pLink->items[i]->attrib[attribute][0];
        pIntSet->intervals[i].high = pLink->items[i]->attrib[attribute][1];
		pIntSet->intervals[i].density = pLink->items[i]->attrib[attribute][2];
		assert(pLink->items[i]->attrib[attribute][1] > pLink->items[i]->attrib[attribute][0]);
		
        pIntSet->intervals[i].label = pLink->items[i]->label;
    };
};

void udt_labelProb(UDTDataLinkSet *pLink, double *labelProb)
{
	int i;

	memset(labelProb, 0, sizeof(double)*pLink->labelCount);
	if (pLink->linkCount == 0)
		return;


    for (i = 0; i < pLink->linkCount; ++i) 
        labelProb[pLink->items[i]->label]++;	


	for (i = 0; i < pLink->labelCount; ++i) 
		labelProb[i] /= pLink->linkCount;
};	

int udt_stopTrain(UDTDataLinkSet *pLink)
{
    int i;
    double entropySum = 0;
    double labelProb[MAX_LABEL];
    if (pLink->linkCount == 0) 
        return 1;
	udt_labelProb(pLink, labelProb);

    for (i = 0; i < pLink->labelCount; ++i)  {
//		printf("labeProb[%d]  %lf ", i, labelProb[i]);
		
        if (labelProb[i] != 0) 
            entropySum += -labelProb[i]*log(labelProb[i]);
	};
//	printf("\n");

    if (entropySum < STOP_CRITERA)
        return 1;
    else
        return 0;        
};



void udt_train(UDTDataLinkSet *pLink, UDTTreeLink pRoot, int *attribUsed)
{
	UDTIntervalSet *pIntSet;
	UDTPointSet *pPointSet;
    UDTDataLinkSet *pLinkLeft, *pLinkRight;
	double *attribBuf = (double*)malloc(pLink->linkCount*sizeof(double));


    int i;
    double min = 1000000, result;
    double bestSplitPoint, splitPoint = -1;
    int splitAttrib = -1;


    if (udt_stopTrain(pLink)) {
        pRoot->testAttrib = -1;
        pRoot->labelProb = (double*) malloc (sizeof(double)*pLink->labelCount);
        pRoot->pLeft = pRoot->pRight = 0;
		udt_labelProb(pLink, pRoot->labelProb);

        return;
    };


    pIntSet = (UDTIntervalSet*) malloc(sizeof(UDTIntervalSet));
    pPointSet = (UDTPointSet*) malloc(sizeof(UDTPointSet));
    for (i = 0; i < pLink->attribCount; ++i) {
        if (attribUsed[i] >= max_attrib_used) 
            continue;
        udt_DataLinkSet_to_IntervalSet(pLink, pIntSet, i);
        udt_calcEndPointList(pIntSet, pPointSet);
        result = udt_calcEntropy(pPointSet, &splitPoint);
        if (result < min) {
            min = result;
            bestSplitPoint = splitPoint;
            splitAttrib = i;
        };
    };

//    printf("min entropy %lf, splitPoint %lf, splitAttrib %d, attribUsed %d\n", min, bestSplitPoint, splitAttrib
//			, attribUsed[splitAttrib]);

    free(pIntSet);
    free(pPointSet);

    if (splitAttrib == -1) {
        pRoot->testAttrib = -1;
        pRoot->labelProb = (double*) malloc (sizeof(double)*pLink->labelCount);
        pRoot->pLeft = pRoot->pRight = 0;
		udt_labelProb(pLink, pRoot->labelProb);

        return;
    };


    attribUsed[splitAttrib]++;

    pRoot->splitPoint = bestSplitPoint;
    pRoot->testAttrib = splitAttrib;
    pRoot->pLeft = pRoot->pRight = 0;

    pLinkLeft = (UDTDataLinkSet*) malloc(sizeof(UDTDataLinkSet));
    pLinkLeft->linkCount = 0;
    pLinkLeft->labelCount =  pLink->labelCount;
	pLinkLeft->attribCount = pLink->attribCount;

    for (i = 0; i < pLink->linkCount; ++i) {
		attribBuf[i] = pLink->items[i]->attrib[splitAttrib][1];		
        if (pLink->items[i]->attrib[splitAttrib][0] < bestSplitPoint) {
            pLinkLeft->items[pLinkLeft->linkCount] = pLink->items[i];
  	
			if (pLink->items[i]->attrib[splitAttrib][1] > bestSplitPoint)
				pLink->items[i]->attrib[splitAttrib][1] = bestSplitPoint;
				
            pLinkLeft->linkCount++;
        };
	};

  
    if (pLinkLeft->linkCount > 0) {
        pRoot->pLeft = (UDTTreeLink) malloc(sizeof(UDTTreeObject));
        udt_train(pLinkLeft, pRoot->pLeft, attribUsed);
    };

  	
	for (i = 0; i < pLink->linkCount; ++i)
		pLink->items[i]->attrib[splitAttrib][1] = attribBuf[i];


    free(pLinkLeft);

    pLinkRight = (UDTDataLinkSet*) malloc(sizeof(UDTDataLinkSet));
    pLinkRight->linkCount = 0;
    pLinkRight->labelCount =  pLink->labelCount;
	pLinkRight->attribCount = pLink->attribCount;
    for (i = 0; i < pLink->linkCount; ++i) {
		attribBuf[i] = pLink->items[i]->attrib[splitAttrib][0];				
        if (pLink->items[i]->attrib[splitAttrib][1] > bestSplitPoint) {
            pLinkRight->items[pLinkRight->linkCount] = pLink->items[i];

 			if (pLink->items[i]->attrib[splitAttrib][0] < bestSplitPoint)			
				pLink->items[i]->attrib[splitAttrib][0] = bestSplitPoint;			
            pLinkRight->linkCount++;
        };
	};
    if (pLinkRight->linkCount > 0) {
        pRoot->pRight = (UDTTreeLink) malloc(sizeof(UDTTreeObject));
        udt_train(pLinkRight, pRoot->pRight, attribUsed);
    };    


	for (i = 0; i < pLink->linkCount; ++i)
		pLink->items[i]->attrib[splitAttrib][0] = attribBuf[i];


    free(pLinkRight);
	free(attribBuf);
    attribUsed[splitAttrib]--;    
};



